生日攻擊

生日攻擊是密碼學的一種破譯手段，利用了機率論中的生日問題，用於干擾兩個或以上群體之間的通訊。此攻擊是對固定的重新排列模式作隨機嘗試攻擊，仰賴較高的命中率（鴿籠原理）。生日攻擊可在${\textstyle {\sqrt {2^{n}}}=2^{n/2}}$等級的時間內找到雜湊碰撞，低於原像攻擊的 ${\textstyle 2^{n}}$。有研究給出一個籠統（但尚存爭議）的估計，表示量子電腦能夠進行生日攻擊，進而可以破解防雜湊碰撞的抵禦，並能把時間壓縮到 ${\textstyle {\sqrt[{3}]{2^{n}}}=2^{n/3}}$ 的等級。

理解問題

主條目：生日問題

舉例：當老師問一個有30名學生的班級（n = 30）每個人的生日在哪一天（為簡便，此處省略閏年）以確定是否有兩個學生同一天生日（對應碰撞 ）。從直覺角度考慮，機率看起來很小。若老師選擇特定日期（例如9月16日），則至少有一名學生在那天出生的概率是$1-(364/365)^{30}$，約為7.9%。但是，與直覺相反的是，至少一名學生和另外任意一名學生有著相同生日的概率大約為70.63%（n = 30時），從方程 $1-{\frac {365!}{(365-n)!\cdot 365^{n}}}$中可看出。

數學

定函式$f$，攻擊目標是找到符合$f(x_{1})=f(x_{2})$的兩個不同輸入值$x_{1},x_{2}$。這一對$x_{1},x_{2}$被稱之為碰撞。找出一對碰撞的方法可以是隨機或偽隨機地輸入不同的數值，直到找出至少兩個相同的結果為止。但由於生日問題，這種方法的效率不高。明確的說，若函式$f(x)$所擁有的$H$的不同輸出有著相同可能性且$H$足夠大，要取得符合$f(x_{1})=f(x_{2})$的一對不同的自變數$x_{1}$和$x_{2}$，函式平均需要大約$1.25{\sqrt {H}}$個不同個自變數。

思考下面一個實驗。從下列的H數集中隨機均勻地選擇n個值，因此將允許重複。使p（n; H）成為此實驗中至少一個值被選擇多於一次的概率。則概率可估計為

$p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}$

使n（p; H）為將選擇的最小數值，這種情況下找到碰撞的概率至少為 p。通過顛倒上方的表達式，可得到了下列估計公式：

$n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}$

將碰撞概率設為0.5，將得到

$n(0.5;H)\approx 1.1774{\sqrt {H}}$

使Q（H）成為在尋找首次碰撞前所期望的值的數量。此數量可通過下列公式進行估計：

$Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}$

舉例：若使用64位元雜湊，則估計將有1.8 × 10¹⁹個不同的輸出。若這些輸出均可能發生（理想情況下），則攻擊者「僅僅」需要約50億次嘗試（5.38 × 10⁹）就能通過暴力攻擊生成碰撞。此值被稱為 生日界限（birthday bound）而對於n位密碼則需要2^n/2次。下列舉出其他例子

位數	可能輸出（H）	期望的隨機碰撞可能性 （2安全係數）（p）
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
16	216 (~6.5 x 104)	<2	<2	<2	<2	<2	11	36	190	300	430
32	232 （~4.3 × 109）	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	264 （~1.8 × 1019）	6	190	6100	190,000	6,100,000	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	2128 （~3.4 × 1038）	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	2256 （~1.2 × 1077）	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	2384 （~3.9 × 10115）	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	2512 （~1.3 × 10154）	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

表格展示了需要達到給定成功可能性的雜湊數量n(p)，且假設所有雜湊均有相同概率。為了比較，通常一塊硬碟的不可修正位元錯誤率為10⁻¹⁸至10⁻¹⁵。理論上說，使用128位元的MD5雜湊或通用唯一辨識碼將在8200億份文件時得到破解，即使它們的可能輸出還要更多。

顯而易見，若函式的輸出不平均分布，碰撞則可能將被更快找到。雜湊函式的「平衡」概念量化了其能抵禦生日攻擊（攻擊平均的金鑰分布）的次數。然而，確定雜湊函式的平衡將需要計算所有輸入，因此這種方法對於諸如MD及SHA系的流行雜湊函式是不切實際的。 當計算$n(p;H)$中的子表達式$\ln {\frac {1}{1-p}}$翻譯到常見的程式語言如log(1/(1-p))下，公式由於有效位遺失對較小的$p$的計算精度不高。例如，當log1p（如C99中一樣）可用時，應直接使用可達到相同效果的表達式-log1p(-p)。 If this is not done, the first column of the above table is computed as zero, and several items in the second column do not have even one correct significant digit.

原始碼範例

下列是能準確生成上方表格中大多數數值的Python函式：

from math import log1p, sqrt

def birthday(probability_exponent, bits):
    probability = 10.0**probability_exponent
    outputs = 2.0**bits
    return sqrt(2.0*outputs*-log1p(-probability))

若代碼儲存在命名為birthday.py的檔案中，使用者可和下面的例子一樣互動執行此程式：

$ python -i birthday.py
>>> birthday(-15, 128)
824963474247.1193
>>> birthday(-6, 32)
92.68192319417072

簡單估計

一項經驗法則可適用於此關係中的心算流程

$p(n)\approx {n^{2} \over 2H}$

可覆寫為

$H\approx {n^{2} \over 2p(n)}$.

或

$n\approx {\sqrt {2H\times p(n)}}$.

此公式在概率小於等於0.5時有效。

此近似方案在使用指數時可輕易使用。例如，假設構建32位元雜湊（$H=2^{32}$）且希望碰撞概率為100萬分之一（$p\approx 2^{-20}$），則最多需要多少份文件？

$n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5$

即與正確答案93次近似。

數位簽章敏感度

數位簽章可對生日攻擊十分敏感。設想一條被首次計算$f(m)$（$f$為密碼雜湊函式）所簽章的資訊，且隨後又使用了一些金鑰來簽章$f(m)$。假設愛麗絲與鮑伯牽涉到簽章詐騙合同。馬洛里準備了一份正常合同$m$和一份偽造合同$m'$。馬洛里隨後發現$m$所在的位置數可在不改變原意的情況下（如插入逗號、清空行、在句後增加一兩個空格、替換同義詞等等）被更改。通過結合這些更改，她可新建諸多$m$的變體且均為正常合同。

相似情況下，馬洛里也為偽造合同$m'$新建了諸多變體。她隨後應用雜湊函式到所有變體直到她找到與正常合同有著相同雜湊值$f(m)=f(m')$的偽造合同位置。她隨後將正常合同帶給鮑勃簽章。在鮑勃簽章完後，馬洛里將簽章取下並依附到偽造簽章上。此簽章「證實了」鮑勃簽署了偽造合同。

此例中，攻擊概率與原始的生日問題稍有不同，因為馬洛里將在尋找兩份具有相同雜湊的正常合同與偽造合同時將一無所獲。馬洛里的策略是生成一份偽造和一份正常的合同。生日問題公式適用於$n$為合同對數的情況下。但馬洛里所生成的雜湊數實際上為$2n$。

為避免這種攻擊，用於簽章方案的雜湊函式的輸出長度應夠大以從計算角度防止生日攻擊。換言之，位數應為防止普通暴力破解所需位數的兩倍。

除了使用更大的位數長度外，簽章者（鮑勃）可以在簽章前做出一些隨機且無害的更改，並且在自己的手上留下一份合同副本以在法庭上展示出他的簽章與正常合同上的匹配，而不匹配偽造合同。

離散對數的波拉德ρ演算法是使用生日攻擊以計算離散對數的演算法。

另請參閱

• 碰撞攻擊
• 中途相遇攻擊

參考文獻

• 米希爾·貝拉爾，《等一下：雜湊函式平衡及其對生日攻擊的影響》（Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks） EUROCRYPT 2004: pp401–418
• 《應用密碼學》, 第二版。（Applied Cryptography, 2nd ed.） 布魯斯·施奈爾所著

外部連結

• "What is a digital signature and what is authentication?" 來自RSA安全加密的常見問題集。
• "Birthday Attack" （頁面存檔備份，存於網際網路檔案館） X5網路加密問答